COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "let.pub" source
C00013 ENDMK
C⊗;
.require "let.pub" source
∂AIL Dr. A. Colmerauer↓Groupe d'Intelligence Artificielle
↓Unite d'Enseignement et de Recherche
↓70, Route Leon-Lachamp↓13 - Marseille (9 e)↓FRANCE∞

Dear Alain:

	I see that contrary to my expectation, they got the money
and the Queen Mary conference will be held.  Also contrary to my
expectation, it doesn't seriously overlap the AI and philosophy
conference in Vancouver, so I shall come to it Thursday and Friday.
Anyway, I hope to see you there, and maybe you'll be able to go
back to your original plan and bring Colette.

	After I finished my lectures in Sweden, I got around to trying
Prolog.  I guess undertaking to lecture to the university presidents
was a psychological hazard, and I had been working on extending
non-monotonic reasoning to tolerating ambiguity.  Anyway I didn't
really get around to Prolog in Marseilles.

	I wrote a Lisp eval program in prolog and got it working
in Sweden, and Antonio Porto and Luis Pereira helped me rewrite
it in purer form.  However, that isn't very interesting except as
an exercise.

	Pereira and Porto showed me a paper about selective backtracking
and gave as an example coloring a map.  I suppose you have seen the
paper.  Map coloring turns out to exemplify some problems with the
Kowalski doctrine that "program = logic + control".  Pereira and
Porto point out that ordinary Prolog backtracking doesn't work well
because when a conflict is encountered, the backtracking will often
take back colorings which are unrelated to the conflict.  Their
selective backtracking works better, but most maps including that
of Europe, the U.S.A., South America and Africa can be colored without
any backtracking at all by the following algorithm.

	Note that coloring any country with three or fewer neighbors can
be postponed till after its neighbors have been colored, because no
matter how they are colored, there is always a color left.  Therefore,
we can delete from a map all countries with three or fewer neighbors
getting a reduced map, which may again have countries with three or
fewer neighbors and hence be further reducible.  Repeating this process
eventually reduces all the afore-mentioned maps to the null map, so
the countries can be colored in reverse order to their elimination
without any backtracking except that involved in finding a color for
a country that doesn't conflict with those assigned to its immediate
neighbors.

	It is easy enough to write a Prolog program that carries out
this algorithm.  I have done so, and it colors the U.S. west of the
Mississipi without any trouble, although it runs out of storage on
the full map of the U.S.  Compiling or some lesser optimization would
no doubt fix it.  However, it is more interesting to try to generalize
the algorithm to logic programs in general.

	I haven't concluded how far the generalization can be carried,
but at least we have the following.
The Pereira-Porto program consists of two parts.  A collection of
assertions such as %2next(y,b)%1 which state what pairs of colors
are compatible, and a statement which for their particular map is

goal(R1,R2,R3,R4,R5,R6) ← next(R1,R2),next(R1,R3), ...

expressing the fact that neighboring countries must have compatible
colorings.

	This suggests introducing the notion of a "postponable variable"
which is such that we can prove a theorem about the literals in which
it occurs.  Namely, for any values of the other variables occurring
in these literals, there is a value for this variable that satisfies
these literals.  Clearly any variables for which we can prove
postponability theorems can be removed from the body of the clause.
Moreover, just as with colors of countries, removing some variables
may make other variables postponable permitting reduction to a form
where there are no postponable variables, which in favorable cases
will be none.  Opposite to postponable variables are variables whose
values are determined by a subset of the clauses, and these should
be evaluated first.  Of course, in their present form, these notions
only apply to rather special Prolog programs, but they certainly
suggest another form of intelligent control.

	However, there's more than that in the coloring example.
Actually it is possible to eliminate not merely countries with
three or fewer neighbors but also countries with four neighbors.
Suppose we have colored the neighbors of a country with four
neighbors, and we wish to color that country.  Unless all four
colors have been used on the neighbors there is no problem, so
assume all four have been used, and that yellow is opposite blue
and green opposite red.  Consider all countries that can be
reached from the yellow neighbor by paths going through yellow
and blue countries on the part of the map that has been colored.
This set of countries is called the %2yellow-blue Kempe component%1
of the yellow neighbor.  Either it contains the blue neighbor or
not.  If not we interchange yellow and blue in the yellow-blue
Kempe component.  This introduces no conflicts but changes the
yellow neighbor to blue and leaves yellow available to color the
new country.  If the yellow-blue component includes the blue
neighbor, then the Jordan curve theorem tells us that the green-red
component of the green neigbor cannot contain the red neigbor, so
a red-green interchange in this component will free green for
the new country.  These %2Kempe transformation%1 were introduced
in Kempe's 1890? false proof of the four color theorem and have
been important in all subsequent work on the theorem.

	The question that arises is whether this method can be
regarded as control added to the logic of the Pereira-Porto program
and, if so, how should it be expressed.  Notice that unlike the
previous method, it isn't applicable to coloring graphs in general
but depends on the fact that we're talking about planar graphs.
Indeed countries with four neighbors can't be cavalierly eliminated
from maps on the torus.  Its backtracking interpretation is a
complicated strategy of changing the values of certain variables
connected in certain ways by relations, and there is no obvious
generalization beyond the coloring program.  On the other hand
there may be some way of expressing it as a metalogical
strategy, and proposed ways of expressing control should be tested
as to whether they can express what we may call the "Kempe
algorithm".

	Unless someone tells me that all this is beside the point,
I will probably talk about it briefly at the Queen Mary conference.

	Carolyn joins me in thanking you and Colette for all your
hospitality.

	Also please tell me your home mailing address.

.reg